The author frames tokenizer design as an integer linear program, relaxes it to a continuous LP, and uses cutting planes to close the gap between fractional and integral solutions. They automate cut discovery with Codex, apply cycle constraints on overlapping token edges, and report provably optimal tokenizers on small pretokenized datasets.

• BPE, despite being greedy, actually gets within 1% of the true optimal tokenizer, as revealed by casting tokenization as an ILP with a provable lower bound.
• The LP relaxation plus rounding gives a feasible upper bound, and cutting planes (constraints violated by fractional solutions but satisfied by all integral ones) tighten the gap between the two.
• Codex was used to automatically discover these cutting planes by brute-forcing small word pairs/triplets and solving auxiliary LPs to find maximally violated constraints, rather than deriving them by hand.
• Results are only provably optimal under a fixed pretokenization scheme, since dropping that assumption would make the LP intractably large.